{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Index of a Valid Split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合法分割的最小下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果元素 <code>x</code>&nbsp;在长度为 <code>m</code>&nbsp;的整数数组 <code>arr</code>&nbsp;中满足 <code>freq(x) * 2 &gt; m</code>&nbsp;，那么我们称 <code>x</code>&nbsp;是 <strong>支配元素</strong>&nbsp;。其中&nbsp;<code>freq(x)</code>&nbsp;是 <code>x</code>&nbsp;在数组 <code>arr</code>&nbsp;中出现的次数。注意，根据这个定义，数组 <code>arr</code>&nbsp;<strong>最多</strong>&nbsp;只会有 <strong>一个</strong>&nbsp;支配元素。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>nums</code>&nbsp;，数据保证它含有一个支配元素。</p>\n",
    "\n",
    "<p>你需要在下标 <code>i</code>&nbsp;处将&nbsp;<code>nums</code>&nbsp;分割成两个数组&nbsp;<code>nums[0, ..., i]</code> 和&nbsp;<code>nums[i + 1, ..., n - 1]</code>&nbsp;，如果一个分割满足以下条件，我们称它是&nbsp;<strong>合法</strong>&nbsp;的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; n - 1</code></li>\n",
    "\t<li><code>nums[0, ..., i]</code>&nbsp;和&nbsp;<code>nums[i + 1, ..., n - 1]</code>&nbsp;的支配元素相同。</li>\n",
    "</ul>\n",
    "\n",
    "<p>这里，&nbsp;<code>nums[i, ..., j]</code>&nbsp;表示 <code>nums</code>&nbsp;的一个子数组，它开始于下标&nbsp;<code>i</code>&nbsp;，结束于下标&nbsp;<code>j</code>&nbsp;，两个端点都包含在子数组内。特别地，如果&nbsp;<code>j &lt; i</code>&nbsp;，那么&nbsp;<code>nums[i, ..., j]</code>&nbsp;表示一个空数组。</p>\n",
    "\n",
    "<p>请你返回一个 <strong>合法分割</strong>&nbsp;的 <strong>最小</strong>&nbsp;下标。如果合法分割不存在，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2,2,2]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。\n",
    "数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 * 2 &gt; 3 。\n",
    "数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 * 2 &gt; 1 。\n",
    "两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。\n",
    "下标 2 是合法分割中的最小下标。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,1,3,1,1,1,7,1,2,1]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>我们将数组在下标 4 处分割，得到 [2,1,3,1,1] 和 [1,7,1,2,1] 。\n",
    "数组 [2,1,3,1,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 &gt; 5 。\n",
    "数组 [1,7,1,2,1] 中，元素 1 是支配元素，因为它在数组中出现了 3 次，且 3 * 2 &gt; 5 。\n",
    "两个数组 [2,1,3,1,1] 和 [1,7,1,2,1] 都有与 nums 一样的支配元素，所以这是一个合法分割。\n",
    "下标 4 是所有合法分割中的最小下标。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [3,3,3,3,7,2,2]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>没有合法分割。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>nums</code>&nbsp;有且只有一个支配元素。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-index-of-a-valid-split](https://leetcode.cn/problems/minimum-index-of-a-valid-split/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-index-of-a-valid-split](https://leetcode.cn/problems/minimum-index-of-a-valid-split/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,2]', '[2,1,3,1,1,1,7,1,2,1]', '[3,3,3,3,7,2,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "       \n",
    "        counter = 1 \n",
    "        dominant= nums[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            if dominant == nums[i]:\n",
    "                counter+=1\n",
    "            else:\n",
    "                counter-=1\n",
    "                if counter<=0:\n",
    "                    counter = 1\n",
    "                    dominant = nums[i]\n",
    "        dominantCounter = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == dominant:\n",
    "                dominantCounter+=1\n",
    "        left = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            if num == dominant:\n",
    "                left+=1\n",
    "            if left*2>i+1 and (dominantCounter-left)*2>len(nums)-i-1:\n",
    "                return i\n",
    "            \n",
    "                \n",
    "        \n",
    "        return -1\n",
    "            \n",
    "            \n",
    "                    \n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 摩尔投票法求出支配元素\n",
    "        x = 0\n",
    "        c = 0\n",
    "        for num in nums:\n",
    "            if num == x:\n",
    "                c += 1\n",
    "                continue\n",
    "            \n",
    "            c -= 1\n",
    "            if c == -1:\n",
    "                x = num\n",
    "                c = 1\n",
    "        \n",
    "        c = nums.count(x)\n",
    "        n = len(nums)\n",
    "\n",
    "        cc = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i] == x:\n",
    "                cc += 1\n",
    "            \n",
    "            if cc*2 > i+1 and (c - cc)*2 > n-1-i:\n",
    "                return i\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        # 摩尔投票法求出支配元素\n",
    "        x = 0\n",
    "        c = 0\n",
    "        for num in nums:\n",
    "            if num == x:\n",
    "                c += 1\n",
    "                continue\n",
    "            \n",
    "            c -= 1\n",
    "            if c == -1:\n",
    "                x = num\n",
    "                c = 1\n",
    "        \n",
    "        # 计数\n",
    "        c = nums.count(x)\n",
    "        n = len(nums)\n",
    "\n",
    "        cc = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i] == x:\n",
    "                cc += 1\n",
    "            \n",
    "            if cc*2 > i+1 and (c - cc)*2 > n-1-i:\n",
    "                return i\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return -1\n",
    "        # 寻找支配元素 O(n)\n",
    "        elem, cnt = 0, 1\n",
    "        for x in nums:\n",
    "            if x != elem:\n",
    "                cnt -= 1\n",
    "                if cnt == 0:\n",
    "                    elem = x\n",
    "                    cnt = 1\n",
    "            else:\n",
    "                cnt += 1\n",
    "        # 记录支配元素出现的次数\n",
    "        cnt = 0\n",
    "        for x in nums:\n",
    "            if x == elem:\n",
    "                cnt += 1\n",
    "        # 若 elem 仅比 nums 的长度多 1 则合法分割不存在，按照题意返回-1\n",
    "        if 2 * cnt <= n + 1:\n",
    "            return -1\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == elem:\n",
    "                cnt += 1\n",
    "            if cnt * 2 > i + 1:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = 1\n",
    "        d = nums[0] # 记录支配元素的值\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if nums[i]==d:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                cnt -= 1\n",
    "            if cnt==0:\n",
    "                d = nums[i]\n",
    "                cnt += 1\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i]==d:\n",
    "                cnt += 1\n",
    "\n",
    "        curCnt = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i]==d:\n",
    "                curCnt += 1\n",
    "            if curCnt*2 > (i+1) and (cnt-curCnt)*2 > n-i-1:\n",
    "                return i\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:return -1\n",
    "        maxnum=0\n",
    "        for i in nums:\n",
    "            if nums.count(i)*2>len(nums):\n",
    "                maxnum=i\n",
    "                countM=nums.count(maxnum)\n",
    "                break\n",
    "        cutline=0\n",
    "        isT=False;leftnum=0;rightnum=countM\n",
    "        while isT==False:\n",
    "            if nums[cutline]==maxnum:\n",
    "                leftnum+=1;rightnum-=1\n",
    "            if leftnum*2>cutline+1 and rightnum*2>len(nums)-cutline-1:\n",
    "                isT=True\n",
    "            cutline+=1\n",
    "            if cutline==len(nums):break\n",
    "        if isT:\n",
    "            return cutline-1\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt, pres = 1, nums[0]\n",
    "        for x in nums[1:]:\n",
    "            if pres == x:\n",
    "                cnt += 1\n",
    "            elif cnt != 0:\n",
    "                cnt -= 1\n",
    "            else:\n",
    "                cnt = 1\n",
    "                pres = x\n",
    "        total, left, res = nums.count(pres), 0, 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            left += nums[i] == pres\n",
    "            if left * 2 > (i + 1) and (total - left) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        val = nums[0]\n",
    "        c = 1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] != val:\n",
    "                c -= 1\n",
    "                if c == 0:\n",
    "                    val = nums[i]\n",
    "                    c = 1\n",
    "            else:\n",
    "                c += 1\n",
    "        total_c = nums.count(val)\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == val:\n",
    "                c += 1\n",
    "            if 2 * c  > i + 1 and 2 * (total_c - c) > n - 1 - i:\n",
    "                return i\n",
    "        return -1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "      candidate = -1\n",
    "      vote = 0\n",
    "      for num in nums:\n",
    "        if candidate == -1:\n",
    "          candidate = num\n",
    "          vote = 1\n",
    "        else:\n",
    "          if candidate == num:\n",
    "            vote += 1\n",
    "          else:\n",
    "            vote -= 1\n",
    "            if vote == 0: candidate = -1\n",
    "      \n",
    "      vote = nums.count(candidate)\n",
    "      cnt = 0\n",
    "      n = len(nums)\n",
    "      for i in range(n-1):\n",
    "        if nums[i] == candidate:\n",
    "          cnt += 1\n",
    "        if cnt * 2 > i + 1 and (vote - cnt) * 2 > n - i - 1:\n",
    "          return i\n",
    "      return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        # 众数 及出现次数\n",
    "        mode, tot = Counter(nums).most_common(1)[0]  # tuple\n",
    "        # 众数在左边出现的次数\n",
    "        freq = 0\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == mode:\n",
    "                freq += 1\n",
    "            # 满足题意\n",
    "            if freq * 2 > i + 1 and (tot - freq) * 2 > n - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x = y = 0\n",
    "        for k, v in Counter(nums).items():\n",
    "            if v > x:\n",
    "                x = v\n",
    "                y = k\n",
    "        cnt = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i] == y:\n",
    "                cnt += 1\n",
    "                if cnt * 2 > (i + 1) and (x - cnt) * 2 > (n - i - 1):\n",
    "                    return i\n",
    "        print(cnt, y)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        c=collections.Counter(nums)\n",
    "        z,zc=-1,-1\n",
    "        for key in c:\n",
    "            if c[key]>zc:\n",
    "                zc=c[key]\n",
    "                z=key   \n",
    "        if zc*2-1==n:\n",
    "            return -1\n",
    "        now=0\n",
    "        for i in range(n-1):\n",
    "            if nums[i]==z:\n",
    "                now +=1\n",
    "                if now*2>i+1 and (zc-now)*2>(n-i-1):\n",
    "                    return i   \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        zhi, total = Counter(nums).most_common(1)[0]\n",
    "        fre1 = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == zhi:\n",
    "                fre1 += 1\n",
    "                if fre1 > (i+1) // 2 and total - fre1 > (len(nums) -i - 1) // 2:\n",
    "                    return(i)\n",
    "        return(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        k, v  = cnt.most_common(1)[0]\n",
    "        if 2*v-1==len(nums):\n",
    "            return -1\n",
    "        a,b=0,0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x==k:\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "            if a>b:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        x, mx = max(Counter(nums).items(),key=lambda p : p[1])\n",
    "        print(x, mx)\n",
    "        l, r = 0, 2 * mx - n\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] == x:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "            else:\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            if l > 0 and r > 0:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = Counter(nums)\n",
    "        mc, su = counter.most_common(1)[0]\n",
    "        # print(mc)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == mc:\n",
    "               cnt += 1 \n",
    "               if cnt * 2 > i + 1 and (su - cnt) * 2 > n - i - 1:\n",
    "                   return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        for k, v in cnt.items():\n",
    "            if v*2>n:\n",
    "                hit_k, hit_v = k, v\n",
    "        print(hit_k, hit_v)\n",
    "        acc = 0\n",
    "        for i in range(0, n-1):\n",
    "            if nums[i]==hit_k:\n",
    "                acc+=1\n",
    "            if acc*2>(i+1) and (hit_v-acc)*2>(n-i-1):\n",
    "                return i\n",
    "            # print(i, acc, acc*2, i+1, (hit_v-acc)*2, n-i-1)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        x, s = Counter(nums).most_common(1)[0]\n",
    "        t, n = 0, len(nums)\n",
    "        for i, c in enumerate(nums, 1):\n",
    "            if c != x:\n",
    "                continue\n",
    "            t += 1\n",
    "            if t * 2 > i and (s - t) * 2 > n - i:\n",
    "                return i - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode,total=Counter(nums).most_common(1)[0]\n",
    "        n=len(nums)\n",
    "        count=0\n",
    "        for i,x in enumerate(nums):\n",
    "            if x==mode:\n",
    "                count+=1\n",
    "            if count*2>i+1 and (total-count)*2>(n-i-1):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        # 获取数组中出现次数最多的元素（支配元素）和其出现次数\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        \n",
    "        freq1 = 0  # 初始化支配元素在当前子数组中的出现次数为 0\n",
    "        \n",
    "        # 线性扫描数组\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode  # 如果当前元素是支配元素，更新出现次数\n",
    "            \n",
    "            # 检查是否满足合法分割的条件\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i  # 返回合法分割的最小下标\n",
    "        \n",
    "        return -1  # 如果没有找到合法分割，返回 -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt=collections.Counter(nums)\n",
    "        mode=max(cnt,key=lambda k:cnt[k])\n",
    "        n_mode=cnt[mode]\n",
    "        n_mode_lf=0\n",
    "        print(mode,n_mode)\n",
    "        for i,num in enumerate(nums):\n",
    "            if num==mode:\n",
    "                n_mode_lf+=1\n",
    "                if n_mode_lf*2>i+1 and (n_mode-n_mode_lf)*2>len(nums)-1-i:\n",
    "                    return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]] += 1\n",
    "        x = -1\n",
    "        for k, v in cnt.items():\n",
    "            if x == -1 or cnt[k] > cnt[x]:\n",
    "                x = k \n",
    "        \n",
    "        f = [0] * (n+1) \n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            f[i] = f[i-1] + int(nums[i-1] == x)\n",
    "        for i in range(1, n):\n",
    "            #print(f[i], f[n]-f[i])\n",
    "            if f[i] * 2 > i and (f[n]-f[i]) * 2 > n-i:\n",
    "                return i - 1\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        target = Counter(nums).most_common()[0][0]\n",
    "        \n",
    "        left, right = 0, nums.count(target)\n",
    "        for i in range(N - 1):\n",
    "            left += nums[i] == target\n",
    "            right -= nums[i] == target\n",
    "            \n",
    "            if left * 2 > (i + 1) and right * 2 > (N - i - 1):\n",
    "                return i\n",
    "        \n",
    "        return -1\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = {}\n",
    "        for n in nums:\n",
    "            if n not in cnt:\n",
    "                cnt[n] = 0\n",
    "            cnt[n] += 1\n",
    "\n",
    "        cnt = sorted(cnt.items(), key=lambda x: x[1], reverse=True)\n",
    "        mode, total = cnt[0]\n",
    "\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        counter = Counter(nums)\n",
    "        dem = 0\n",
    "        maxi = 0\n",
    "        for c in counter:\n",
    "            if counter[c] > maxi:\n",
    "                dem = c\n",
    "                maxi = counter[c]\n",
    "        if counter[dem] * 2 == len(nums) + 1:\n",
    "            return -1\n",
    "        \n",
    "        f0 = counter[dem]\n",
    "        f1 = len(nums) - counter[dem]\n",
    "        diction = {0:0, 1:0}\n",
    "        for i, n in enumerate(nums):\n",
    "            if n == dem:\n",
    "                diction[0] += 1\n",
    "            else:\n",
    "                diction[1] += 1\n",
    "            if diction[0] > diction[1] and f0 - diction[0] > f1 - diction[1]:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        c = Counter(nums)\n",
    "        v, k = max([(v, k) for k, v in c.items()])\n",
    "\n",
    "        if 2 * v - 1 == n:\n",
    "            return -1\n",
    "\n",
    "        l_e = 0\n",
    "        l_other = 0\n",
    "        r_e = v\n",
    "        r_other = n - v\n",
    "        for e in nums:\n",
    "\n",
    "            if e == k:\n",
    "                l_e += 1\n",
    "                r_e -= 1\n",
    "            else:\n",
    "                l_other += 1\n",
    "                r_other -= 1\n",
    "            \n",
    "            if l_e > l_other:\n",
    "                return l_e + l_other - 1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mc_num, mc_cnt = Counter(nums).most_common(1)[0]\n",
    "        crt_cnt = 0\n",
    "        n = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == mc_num:\n",
    "                crt_cnt += 1\n",
    "            if crt_cnt > i + 1 - crt_cnt and ((mc_cnt - crt_cnt) > (n - i - 1 - (mc_cnt - crt_cnt))):\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        len_ = len(nums)\n",
    "        target = mode(nums)\n",
    "        r = nums.count(target)\n",
    "        # 左边的目标数\n",
    "        l = 0\n",
    "        # i是左数组的长度\n",
    "        for i, n in enumerate(nums, 1):\n",
    "            if n == target:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "                if l << 1 > i and r << 1 > len_ - i:\n",
    "                    return i - 1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        #找到这个元素,频率最高\n",
    "        x,c = Counter(nums).most_common(1)[0]\n",
    "        #遍历 nums 第二次\n",
    "        n=len(nums);n1=n-1;t=i=0\n",
    "        for i in range(n1):\n",
    "            leftsize =i+1\n",
    "            if nums[i]==x:\n",
    "                t+=1 \n",
    "                v=t+t\n",
    "                if v>leftsize:\n",
    "                    b=c+c-v\n",
    "                    if b >n-leftsize:\n",
    "                        return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        counter=collections.Counter(nums)\n",
    "        max_freq=max(counter.values())\n",
    "        x=None\n",
    "        for k,f in counter.items():\n",
    "            if f==max_freq:\n",
    "                x=k\n",
    "        cnt=0\n",
    "        n=len(nums)\n",
    "        for i in range(n-1):\n",
    "            if nums[i]==x:\n",
    "                cnt+=1\n",
    "            if cnt*2>i+1 and (counter[x]-cnt)*2>(n-(i+1)):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        #找到这个元素,频率最高\n",
    "        x,c = Counter(nums).most_common(1)[0]\n",
    "        #遍历 nums 第二次\n",
    "        n=len(nums)\n",
    "        n1=n-1\n",
    "        t=i=0\n",
    "        for i in range(n1):\n",
    "            leftsize =i+1\n",
    "            if nums[i]==x:\n",
    "                t+=1 \n",
    "                v=t+t\n",
    "                if v>leftsize:\n",
    "                    b=c+c-v\n",
    "                    if b >n-leftsize:\n",
    "                        return i\n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        n=len(nums)\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums,1):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i and (total - freq1) * 2 > n- i:\n",
    "                return i-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt=collections.Counter(nums)\n",
    "\n",
    "        n=len(nums)\n",
    "        \n",
    "        arr=[]\n",
    "        for x in cnt:\n",
    "            if cnt[x]*2>=n:\n",
    "                t=x\n",
    "                c=cnt[x]\n",
    "\n",
    "        k=0\n",
    "        \n",
    "        for i,v in enumerate(nums):\n",
    "\n",
    "            l=i+1        \n",
    "            r=n-l\n",
    "            if v==t:\n",
    "                k=k+1\n",
    "            if k*2>l and (c-k)*2>r:\n",
    "                return i\n",
    "        \n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n, j = len(nums), 1\n",
    "        x, m = Counter(nums).most_common(1)[0]\n",
    "        for i in range(n):\n",
    "            if nums[i] == x:\n",
    "                if j * 2 > i + 1 and (m - j) * 2 > n - i - 1:\n",
    "                    return i\n",
    "                j += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter(nums)\n",
    "        maxNum, maxCnt = counter.most_common(1)[0]\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == maxNum:\n",
    "                left += 1 \n",
    "                if left * 2 > i + 1 and (maxCnt - left) * 2 > n - i - 1:\n",
    "                    return i \n",
    "        return - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        n=len(nums)\n",
    "        f=freq1 = 0\n",
    "        for i, x in enumerate(nums,1):\n",
    "            f += x == mode\n",
    "            t=f+f\n",
    "            if t > i and total+total-t> n- i:\n",
    "                return i-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        #找到这个元素,频率最高\n",
    "        x,c = Counter(nums).most_common(1)[0]\n",
    "        #遍历 nums 第二次\n",
    "        n=len(nums);n1=n-1;t=i=0\n",
    "        for i,v in enumerate(nums,1):\n",
    "            if v==x:\n",
    "                t+=1 \n",
    "                v=t+t\n",
    "                if v>i:\n",
    "                    b=c+c-v\n",
    "                    if b >n-i:\n",
    "                        return i-1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        # 支配元素 = 众数\n",
    "\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter(nums)\n",
    "        maxNum = counter.most_common(1)[0][0]\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == maxNum:\n",
    "                left += 1 \n",
    "                if left * 2 > i + 1 and (counter[maxNum] - left) * 2 > n - i - 1:\n",
    "                    return i\n",
    "        return - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        len_ = len(nums)\n",
    "        target = mode(nums)\n",
    "        r = nums.count(target)\n",
    "        # 左边的目标数\n",
    "        l = 0\n",
    "        # i是左边的总数\n",
    "        for i, n in enumerate(nums, 1):\n",
    "            if n == target:\n",
    "                l += 1\n",
    "                r -= 1\n",
    "                if l * 2 > i and r * 2 > len_ - i:\n",
    "                    return i - 1\n",
    "        return -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        m, t = Counter(nums).most_common(1)[0]\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == m:\n",
    "                cnt += 1\n",
    "            if (cnt * 2) > (i + 1) and ((t - cnt) * 2 > (n - i - 1)):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        t = max(cnt,key = lambda x:cnt[x])\n",
    "        tem = 0\n",
    "        for i in range(n-1):\n",
    "            if nums[i]==t:\n",
    "                tem +=1\n",
    "            if tem*2>(i+1) and (cnt[t]-tem)*2>(n-i-1):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        # 支配元素 = 众数\n",
    "\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        n = len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > n - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        target, cnt = Counter(nums).most_common(1)[0]\n",
    "        left_cnt = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if x == target:\n",
    "                left_cnt += 1\n",
    "                if left_cnt * 2 > i + 1 and (cnt - left_cnt) * 2 > len(nums) - i - 1:\n",
    "                    return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums). most_common(1)[0]\n",
    "        cnt = 0;\n",
    "        for i, x in enumerate(nums):\n",
    "            cnt += (x == mode)\n",
    "            if (cnt * 2 > i + 1 and (total - cnt) * 2 > len(nums) - i - 1):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\r\n",
    "        #freq1 * 2 > i + 1\r\n",
    "        #freq2 * 2 > n - i - 1\r\n",
    "        #freq * 2 = freq1 * 2 + freq2 * 2 > n\r\n",
    "        freq, total = Counter(nums).most_common(1)[0]\r\n",
    "        freq1 = 0\r\n",
    "        n = len(nums)\r\n",
    "        for i, num in enumerate(nums):\r\n",
    "            freq1 += num == freq\r\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > n - i - 1:\r\n",
    "                return i\r\n",
    "        return -1\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        i,n=0,0\n",
    "        for j,k in cnt.items():\n",
    "            if k>n:\n",
    "                n=k\n",
    "                i=j\n",
    "        ans=-1\n",
    "        temp=0\n",
    "        for j in range(len(nums)):\n",
    "            if nums[j]==i:\n",
    "                temp+=1\n",
    "            if temp*2>j+1 and (n-temp)*2>len(nums)-j-1:\n",
    "                return j\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        v = max(cnt, key = lambda x:cnt[x])\n",
    "        tot = cnt[v]\n",
    "        n = len(nums)\n",
    "        c = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == v:\n",
    "                c += 1\n",
    "            if c * 2 > i + 1 and (tot - c) * 2 > (n - i - 1):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = collections.Counter(nums) \n",
    "        n = len(nums) \n",
    "        u = nums[0]\n",
    "        for x, y in cnt.items():\n",
    "            if cnt[x] > cnt[u]:\n",
    "                u = x \n",
    "        if cnt[u] * 2 <= n:\n",
    "            return -1 \n",
    "        cnt1 = defaultdict(int)\n",
    "        v = nums[0]\n",
    "        for l in range(n):\n",
    "            cnt1[nums[l]] += 1\n",
    "            if cnt1[v] < cnt1[nums[l]]:\n",
    "                v = nums[l]\n",
    "            if v == u and (cnt1[v] * 2 > l + 1) and (cnt[u] - cnt1[v]) * 2 > n - l -1:\n",
    "                return l \n",
    "        return -1 \n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxcnt = 0\n",
    "        maxnum = -1\n",
    "        left = [-1]*n\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            if(nums[i] not in mapping):\n",
    "                mapping[nums[i]] = 1\n",
    "            else:\n",
    "                mapping[nums[i]] += 1\n",
    "            if(maxcnt < mapping[nums[i]]):\n",
    "                maxcnt = mapping[nums[i]]\n",
    "                maxnum = nums[i]\n",
    "            if(maxcnt*2 > i+1):\n",
    "                left[i] =  maxnum\n",
    "        maxcnt = 0\n",
    "        maxnum = -1\n",
    "        right = [-1]*n \n",
    "        mapping = {}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(nums[i] not in mapping):\n",
    "                mapping[nums[i]] = 1\n",
    "            else:\n",
    "                mapping[nums[i]] += 1\n",
    "            if(maxcnt < mapping[nums[i]]):\n",
    "                maxcnt = mapping[nums[i]]\n",
    "                maxnum = nums[i]\n",
    "            if(maxcnt*2 > n-i):\n",
    "                right[i] =  maxnum\n",
    "\n",
    "        for i in range(n-1):\n",
    "            if(left[i] == right[i+1] and left[i] != -1):\n",
    "                return i \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        x, t = Counter(nums).most_common(1)[0]\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        for i in range(n - 1):\n",
    "            if nums[i] == x:\n",
    "               cnt += 1\n",
    "            if cnt * 2 > i + 1 and (t - cnt) * 2 > n - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        pre = [-1] * n\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] * 2 > i + 1:\n",
    "                pre[i] = nums[i]\n",
    "            else:\n",
    "                pre[i] = pre[i - 1] if cnt[pre[i - 1]] * 2 > i + 1 else -1\n",
    "        suf = [-1] * n\n",
    "        cnt.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] * 2 > n - i:\n",
    "                suf[i] = nums[i]\n",
    "            else:\n",
    "                suf[i] = suf[i + 1] if cnt[suf[i + 1]] * 2 > n - i else -1\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if pre[i] != -1 and suf[i + 1] != -1 and pre[i] == suf[i + 1]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        mode, total = Counter(nums).most_common(1)[0]\n",
    "        freq1 = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            freq1 += x == mode\n",
    "            if freq1 * 2 > i + 1 and (total - freq1) * 2 > len(nums) - i - 1:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n_count = dict()\n",
    "        key_element = None\n",
    "        max_count = 0\n",
    "        for n in nums:\n",
    "            if n not in n_count.keys():\n",
    "                n_count[n] = 0\n",
    "            n_count[n] += 1\n",
    "            if n_count[n] > max_count:\n",
    "                key_element = n\n",
    "                max_count = n_count[n]\n",
    "        left_count = 0\n",
    "        right_count = max_count\n",
    "        length = len(nums)\n",
    "        for index in range(length-1):\n",
    "            if nums[index] == key_element:\n",
    "                left_count += 1\n",
    "                right_count -= 1\n",
    "            left_len = index+1\n",
    "            right_len = length-left_len\n",
    "            if 2*left_count > left_len and 2*right_count > right_len:\n",
    "                return index\n",
    "        return -1\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        n = len(nums)\n",
    "        pre = [-1] * n\n",
    "        for i in range(n):\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] * 2 > i + 1:\n",
    "                pre[i] = nums[i]\n",
    "            else:\n",
    "                pre[i] = pre[i - 1] if cnt[pre[i - 1]] * 2 > i + 1 else -1\n",
    "        suf = [-1] * n\n",
    "        cnt.clear()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cnt[nums[i]] += 1\n",
    "            if cnt[nums[i]] * 2 > n - i:\n",
    "                suf[i] = nums[i]\n",
    "            else:\n",
    "                suf[i] = suf[i + 1] if cnt[suf[i + 1]] * 2 > n - i else -1\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            if pre[i] != -1 and suf[i + 1] != -1 and pre[i] == suf[i + 1]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        maxcnt = 0\n",
    "        maxnum = -1\n",
    "        left = [-1]*n\n",
    "        mapping = {}\n",
    "        for i in range(n):\n",
    "            if(nums[i] not in mapping):\n",
    "                mapping[nums[i]] = 1\n",
    "            else:\n",
    "                mapping[nums[i]] += 1\n",
    "            if(maxcnt < mapping[nums[i]]):\n",
    "                maxcnt = mapping[nums[i]]\n",
    "                maxnum = nums[i]\n",
    "            if(maxcnt*2 > i+1):\n",
    "                left[i] =  maxnum\n",
    "        maxcnt = 0\n",
    "        maxnum = -1\n",
    "        right = [-1]*n \n",
    "        mapping = {}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if(nums[i] not in mapping):\n",
    "                mapping[nums[i]] = 1\n",
    "            else:\n",
    "                mapping[nums[i]] += 1\n",
    "            if(maxcnt < mapping[nums[i]]):\n",
    "                maxcnt = mapping[nums[i]]\n",
    "                maxnum = nums[i]\n",
    "            if(maxcnt*2 > n-i):\n",
    "                right[i] =  maxnum\n",
    "\n",
    "        for i in range(n-1):\n",
    "            if(left[i] == right[i+1] and left[i] != -1):\n",
    "                return i \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        题意理解: 如果数组中某个元素出现次数大于数组长度的一半, 它就是支配元素\n",
    "        指针i从0位置开始移动, 维护左侧窗口与右侧窗口的长度, 并在哈希表内统计元素出现的次数\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        # {num:[left_cnt, right_cnt]}  数字 对应 其在左右两侧分别出现的次数\n",
    "        cnt = defaultdict(lambda: [0, 0])\n",
    "        length = [0, n]  # 记录左右两侧的长度\n",
    "        # 遍历数组, 先把所有数字出现次数计算到右侧\n",
    "        for num in nums:\n",
    "            cnt[num][1] += 1\n",
    "\n",
    "        # 再次遍历数组\n",
    "        for i, num in enumerate(nums):\n",
    "            length[0] += 1\n",
    "            length[1] -= 1\n",
    "            cnt[num][0] += 1\n",
    "            cnt[num][1] -= 1\n",
    "            # 判断num是否同为左右两侧的支配数字\n",
    "            if cnt[num][0] * 2 > length[0] and cnt[num][1] * 2 > length[1]:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        map = collections.defaultdict(int)\n",
    "        map2 = collections.defaultdict(int)\n",
    "        for num in nums:\n",
    "            map[num] += 1\n",
    "        \n",
    "        n = len(nums)\n",
    "        target = -1\n",
    "        for key in map:\n",
    "            if map[key] * 2 > n:\n",
    "                target = key\n",
    "                break\n",
    "        if target == -1:\n",
    "            return -1\n",
    "        for i, num in enumerate(nums):\n",
    "            map2[num] += 1\n",
    "            if map2[target] * 2 > i + 1 and (map[target] - map2[target]) * 2 > n-1-i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        d = {}\n",
    "        for item in nums:\n",
    "            if item not in d:\n",
    "                d[item] = 1\n",
    "            else:\n",
    "                d[item] +=1\n",
    "        \n",
    "        l = sorted(d.items(),key = lambda x: x[1],reverse = True)\n",
    "\n",
    "        a = l[0][0]\n",
    "        b = l[0][1]\n",
    "\n",
    "        # print(a,b)\n",
    "\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] == a:\n",
    "                cnt+=1\n",
    "            if 2*cnt>i+1 and 2*(b-cnt)>(len(nums)-i-1):\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        题意理解: 如果数组中某个数字出现次数大于数组长度的一半, 它就是支配元素\n",
    "        指针i从0位置开始移动, 维护左侧窗口与右侧窗口的长度, 并在哈希表内统计两侧数字出现的次数\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        # {num:[left_cnt, right_cnt]}  数字 对应 其在左右两侧分别出现的次数\n",
    "        cnt = defaultdict(lambda: [0, 0])\n",
    "        length = [0, n]  # 记录左右两侧的长度\n",
    "        # 遍历数组, 先把所有数字出现次数计算到右侧\n",
    "        for num in nums:\n",
    "            cnt[num][1] += 1\n",
    "\n",
    "        # 再次遍历数组\n",
    "        for i, num in enumerate(nums):\n",
    "            length[0] += 1\n",
    "            length[1] -= 1\n",
    "            cnt[num][0] += 1\n",
    "            cnt[num][1] -= 1\n",
    "            # 判断num是否同为左右两侧的支配数字\n",
    "            if cnt[num][0] * 2 > length[0] and cnt[num][1] * 2 > length[1]:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        count = Counter(nums)\n",
    "        k = count.most_common(1)[0][0]\n",
    "        preCount = [0 for _ in range(len(nums)+1)]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == k:\n",
    "                preCount[i] = preCount[i-1] + 1\n",
    "            else:\n",
    "                preCount[i] = preCount[i-1]\n",
    "                \n",
    "        for i in range(len(nums)):\n",
    "            if preCount[i+1] *2 > (i+1) and (preCount[-1]-preCount[i+1])*2 > (len(nums)-i-1):\n",
    "                return i \n",
    "        \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        count = Counter(nums)\n",
    "        k = count.most_common(1)[0][0]\n",
    "        preCount = [0 for _ in range(len(nums)+1)]\n",
    "        for i in range(1, len(nums)+1):\n",
    "            if nums[i-1] == k:\n",
    "                preCount[i] = preCount[i-1] + 1\n",
    "            else:\n",
    "                preCount[i] = preCount[i-1]\n",
    "                \n",
    "        for i in range(len(nums)):\n",
    "            if preCount[i+1] *2 > (i+1) and (preCount[-1]-preCount[i+1])*2 > (len(nums)-i-1):\n",
    "                return i \n",
    "        \n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        d={}\n",
    "        for x in nums:\n",
    "            d[x] = d.get(x,0)+1\n",
    "        ls=list(d.items())\n",
    "        ls.sort(key = lambda x:x[1],reverse = True)\n",
    "        freq = 0\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            if x == ls[0][0]:\n",
    "                freq += 1\n",
    "            if freq*2 > i+1 and (ls[0][1]-freq)*2 > n-i-1:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        fre = [0] * len(nums)\n",
    "        zhi = Counter(nums).most_common(1)[0][0]\n",
    "        s = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == zhi:\n",
    "                s += 1\n",
    "            fre[i] = s\n",
    "        for i in range(len(nums)):\n",
    "            if fre[i] > (i+1) // 2 and (fre[-1] - fre[i]) > (len(nums) -i - 1) // 2:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        num_dic = defaultdict(int)\n",
    "        length = len(nums)\n",
    "        freq = nums[0]\n",
    "        for num in nums:\n",
    "            num_dic[num] += 1\n",
    "            if num_dic[num] * 2 > length:\n",
    "                freq = num\n",
    "                break\n",
    "        \n",
    "        prefix_freq = [0] * length\n",
    "        subfix_freq = [0] * length\n",
    "\n",
    "        if nums[0] == freq:\n",
    "            prefix_freq[0] = 1\n",
    "        if nums[-1] == freq:\n",
    "            subfix_freq[0] = 1\n",
    "        for i in range(1, length):\n",
    "            prefix_freq[i] = prefix_freq[i - 1] + 1 if nums[i] == freq else prefix_freq[i - 1]\n",
    "            subfix_freq[i] = subfix_freq[i - 1] + 1 if nums[length - i - 1] == freq else subfix_freq[i - 1]\n",
    "        \n",
    "        # print(prefix_freq)\n",
    "        # print(subfix_freq)\n",
    "\n",
    "        for i in range(length - 1):\n",
    "            if prefix_freq[i] * 2 > i + 1 and subfix_freq[length - 2 - i] * 2 > length - 1 - i:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        num_dic = defaultdict(int)\n",
    "        length = len(nums)\n",
    "        freq = nums[0]\n",
    "        for num in nums:\n",
    "            num_dic[num] += 1\n",
    "            if num_dic[num] * 2 > length:\n",
    "                freq = num\n",
    "                break\n",
    "        \n",
    "        prefix_freq = [0] * length\n",
    "        subfix_freq = [0] * length\n",
    "\n",
    "        if nums[0] == freq:\n",
    "            prefix_freq[0] = 1\n",
    "        if nums[-1] == freq:\n",
    "            subfix_freq[0] = 1\n",
    "        for i in range(1, length):\n",
    "            prefix_freq[i] = prefix_freq[i - 1] + 1 if nums[i] == freq else prefix_freq[i - 1]\n",
    "            subfix_freq[i] = subfix_freq[i - 1] + 1 if nums[length - i - 1] == freq else subfix_freq[i - 1]\n",
    "        \n",
    "        # print(prefix_freq)\n",
    "        # print(subfix_freq)\n",
    "\n",
    "        for i in range(length - 1):\n",
    "            if prefix_freq[i] * 2 > i + 1 and subfix_freq[length - 2 - i] * 2 > length - 1 - i:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumIndex(self, nums: List[int]) -> int:\n",
    "        num_dic = defaultdict(int)\n",
    "        length = len(nums)\n",
    "        freq = nums[0]\n",
    "        for num in nums:\n",
    "            num_dic[num] += 1\n",
    "            if num_dic[num] * 2 > length:\n",
    "                freq = num\n",
    "                break\n",
    "        \n",
    "        prefix_freq = [0] * length\n",
    "        subfix_freq = [0] * length\n",
    "\n",
    "        if nums[0] == freq:\n",
    "            prefix_freq[0] = 1\n",
    "        if nums[-1] == freq:\n",
    "            subfix_freq[0] = 1\n",
    "        for i in range(1, length):\n",
    "            prefix_freq[i] = prefix_freq[i - 1] + 1 if nums[i] == freq else prefix_freq[i - 1]\n",
    "            subfix_freq[i] = subfix_freq[i - 1] + 1 if nums[length - i - 1] == freq else subfix_freq[i - 1]\n",
    "        \n",
    "        # print(prefix_freq)\n",
    "        # print(subfix_freq)\n",
    "\n",
    "        for i in range(length - 1):\n",
    "            if prefix_freq[i] * 2 > i + 1 and subfix_freq[length - 2 - i] * 2 > length - 1 - i:\n",
    "                return i\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
